package Array;

import java.util.HashSet;
import java.util.Set;

/**
 * 128. 最长连续序列
 *
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 * 思路：使用Set数组中的数字
 * 1：使用 HashSet：使用 HashSet 来存储数组中的所有元素，这允许我们在 O(1) 时间内检查某个元素是否存在。
 * 2：检查连续序列：对于每个元素，检查是否存在连续的序列。我们只从序列的起始元素开始检查，即当前元素是序列的起始点。
 * 3：计算连续序列长度：一旦找到起始元素，我们就不断地检查下一个连续的元素是否存在，直到找不到为止。
 */
public class L_128 {

    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        Set<Integer> set = new HashSet<>();
        // 先将数组添加到Set中
        for (int i = 0; i < nums.length ; i++) {
            set.add(nums[i]);
        }
        // 定义最长子序列
        int longestStreak = 0;
        for(int num : nums){
            // 只从序列的起始元素开始检查， 即num-1在Set中不存在值
            if(!set.contains(num-1)){
                int currentNum = num;
                int currentStrek = 1; // 当前长度
                // 当set中包含当前元素的后一个连续元素时，一直循环
                while (set.contains(currentNum+1)){
                    currentNum++;
                    currentStrek++;
                }
                // 循环过后，统计当前最长连续长度
                longestStreak = Math.max(longestStreak,currentStrek);
            }
        }
        return longestStreak;
    }
}
